package com.cg.leetcode;

import org.junit.Test;

import java.util.*;

/**
 * 51.N皇后
 *
 * @author cg
 * @program LeetCode->LeetCode_51
 * @create 2022-08-30 20:24
 **/
public class LeetCode_51 {

    @Test
    public void test51() {
        System.out.println(solveNQueens(1));
        System.out.println(solveNQueens(2));
        System.out.println(solveNQueens(3));
        System.out.println(solveNQueens(4));
        System.out.println(solveNQueens(5));
        System.out.println(solveNQueens(9));
    }

    /**
     * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
     * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
     * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
     * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
     * <p>
     * 示例 1：
     * 输入：n = 4
     * 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
     * 解释：如上图所示，4 皇后问题存在两个不同的解法。
     * <p>
     * 示例 2：
     * 输入：n = 1
     * 输出：[["Q"]]
     * <p>
     * 提示：
     * 1 <= n <= 9
     *
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        result = new ArrayList<>();
        char[][] chessboard = new char[n][n];
        for (char[] chars : chessboard) {
            Arrays.fill(chars, '.');
        }
        helper(chessboard, n, 0);
        return result;
    }

    List<List<String>> result;

    private void helper(char[][] chessboard, int n, int row) {
        if (row == n) {
            result.add(arrayToString(chessboard));
            return;
        }
        for (int col = 0; col < n; col++) {
            // 验证合法就放置
            if (isValid(row, col, n, chessboard)) {
                // 放置
                chessboard[row][col] = 'Q';
                // 下一行
                helper(chessboard, n, row + 1);
                // 回溯
                chessboard[row][col] = '.';
            }
        }
    }

    private boolean isValid(int row, int col, int n, char[][] chessboard) {
        // 不用检查行
        // 检查列
        for (int i = 0; i < row; i++) {
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }
        // 检查右斜线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--,j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        // 检查左斜线
        for (int i = row - 1, j = col + 1; i >=0 && j <= n - 1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    private List<String> arrayToString(char[][] chessboard) {
        List<String> res = new ArrayList<>();
        for (char[] chars : chessboard) {
            res.add(String.valueOf(chars));
        }
        return res;
    }



}
